// ref : https://www.runoob.com/w3cnote/heap-sort.html

#ifndef HEAP_DEMO_HPP
#define HEAP_DEMO_HPP

#include <iostream>

namespace heap {

template <class Iterator, class Value>
void _push_heap(Iterator first, int current_index, int root_index,
                Value value) {
  int parent = (current_index - 1) / 2;
  while (current_index > root_index && *(first + parent) < value) {
    *(first + current_index) = *(first + parent);
    current_index = parent;
    parent = (current_index - 1) / 2;
  }
  *(first + root_index) = value;
}

template <class Iterator, class Value>
void _adjust_heap(Iterator first, int current_index, int len, Value value) {
  int tmp_index = current_index;
  int second_child_index = 2 * current_index + 2;
  while (second_child_index < len) {
    if (*(first + second_child_index) < *(first + second_child_index + 1)) {
      second_child_index--;
    }
    *(first + current_index) = *(first + second_child_index);
    current_index = second_child_index;
    second_child_index = 2 * (second_child_index + 1);
  }
  if (second_child_index == len) {
    *(first + current_index) = *(first + second_child_index - 1);
    current_index = second_child_index - 1;
  }
  _push_heap(first, current_index, tmp_index, value);
}

template <class Iterator> void make_heap(Iterator begin, Iterator end) {
  if (end - begin < 2) {
    return;
  }
  int len = end - begin;
  int parent = (len - 2) / 2;
  while (true) {
    _adjust_heap(begin, parent, len, *(begin + parent));
    if (parent == 0) {
      return;
    }
    parent--;
  }
}
template <class Iterator> void push_heap(Iterator begin, Iterator end) {
  _push_heap(begin, end - begin - 1, 0, *(end - 1));
}
template <class Iterator> void pop_heap(Iterator begin, Iterator end) {
  _adjust_heap(begin, 0, end - begin, *(end - 1));
}

// 堆排序
// 找到最大值
// 起始位置0
// 当前节点位置为i，父节点(i-1)/2， 子节点2i+1, 2i+2;
namespace internal {
void adjust_heap(int *arr, int len) {
  for (int i = len - 1; i >= 1; i--) {
    if (arr[i] > arr[(i - 1) / 2]) {
      int tmp = arr[i];
      arr[i] = arr[(i - 1) / 2];
      arr[(i - 1) / 2] = tmp;
    }
  }
}
void test_print(int *arr, int len) {
  for (int i = 0; i < len; i++) {
    std::cout << " " << arr[i];
  }
  std::cout << std::endl;
}
void sort_heap(int *arr, int len) {
  for (int i = 0; i < len; i++) {
    // test_print(arr, len);
    adjust_heap(arr, len - i);
    // test_print(arr, len);
    int max = arr[0];
    arr[0] = arr[len - i - 1];
    arr[len - i - 1] = max;
    // test_print(arr, len);
    // std::cout << "----------" << std::endl;
  }
}
} // namespace internal

} // namespace heap

#endif // HEAP_DEMO_HPP